The present invention relates to a cryptography-processing method, a cryptography-processing apparatus and a computer program. More particularly, the present invention relates to a cryptography-processing method for increasing the processing speed of scalar multiplication in hyperelliptic curve cryptography, relates to a cryptography-processing apparatus adopting the cryptography-processing method and relates to a computer program implementing the cryptography-processing method.
With recent development of network communication and electronic business transaction systems, assurance of security in communications has becoming an important problem. One of methods to assure security is a cryptography technology. Recently, communications are carried out by using a variety of cryptography techniques.
For example, there has been developed a system in which data is exchanged between an IC card including an embedded cryptography-processing module and a reader/writer by carrying out an authentication process and processes to encrypt or decrypt the exchanged data. In such a system, the reader/writer serves as an apparatus for reading and writing the data from and into the IC card.
An IC card typically carrying out a cryptography process is utilized widely in a variety of gates such as an entrance gate of a train station or shopping centers, raising a strong demand for downsizing of the IC card and a demand for enhancement of the processing speed involving the IC card.
Cryptography methods are divided into two large categories, i.e., a common-key cryptography method and a public-key cryptography method. The common-key cryptography method is also referred to as a symmetrical cryptography method. In the common-key cryptography method, the sender and the receiver both have a common key. A representative of the common-key cryptography method is a DES (Data Encryption Standard). The DES is characterized in that the encryption and decryption processes can be carried out in accordance with all but the same algorithms provided by the DES.
As opposed to the common cryptography key, in the public-key cryptography method or an asymmetrical cryptography method, the sender may have a key different from the key owned by the receiver. Unlike the common-key cryptography method whereby a common key is used in encryption and decryption processes, the public-key cryptography method is advantageous to management of keys because only one specific person needs to hold a secret key, which must be kept secretly. In comparison with the common-key cryptography method, however, the public-key cryptography method entails a low processing speed. Therefore, in general, the public-key cryptography method is widely adopted only in transmission of a secret key and transmission of an object having a small amount of data such as a digital signature. As representatives of the public-key cryptography method, RSA (Rivest-Shamir-Adleman) cryptography and ECC (Elliptic Curve Cryptography) are known.
The elliptic curve cryptography uses an elliptic curve y2=x3+ax+b (where 4a3+27b2≠0) over a prime field and an elliptic curve y2+xy=x3+ax2+b (where b≠0) over two extension fields. A set including an infinity point O added to a point on each of these curves forms a finite group for the addition, and the infinity point O becomes an identity element. In the following description, addition of points in the finite group is expressed by the operator +, and addition (P+Q) of two different points P and Q in the finite group is referred to as addition of points. In particular, addition (P+P=2P) of two the points P in the finite group is referred to as doubling computation of a point. An operation to add the point P to itself k times, that is, an operation to compute P+P+ - - - +P=kP, is referred to as scalar multiplication of a point.
As commonly known, the scalar multiplication can be composed of additions of a point and doubling computations of the point. The addition of points, the doubling computation of a point and the scalar multiplication of a point in affine coordinates (x, y) or projective coordinates (X, Y, Z) on an elliptic curve over the prime field and an elliptic curve over the two extension fields are described in IEEE P1363/D13 Standard Specifications for Public Key Cryptography.
As a method of generalizing the elliptic curve cryptography, Koblitz and Cantor have proposed an HECC (hyperelliptic curve cryptography) method. The hyperelliptic curve cryptography method is described in Non-Patent Documents 1 and 2.
Let P be a point on an elliptic curve defined over a finite field Fq and Q be equal to kP (kεZ), that is, Q be a result of scalar multiplication of the point P. In this case, a problem of finding k from Q can be solved as a discrete logarithmic problem. On the other hand, let D1 be a divisor equal to a linear sum of points in the hyperelliptic curve cryptography and D2 be a divisor defined as a scalar multiplication kD1. In this case, a problem of finding k from D2 can be treated as a discrete logarithmic problem in a Jacobian variety on the hyperelliptic curve and handling as public-key cryptography is possible.
In the case of hyperelliptic curves, a value characterizing a curve is referred to as a genus g. Let q be equal to pn (q=pn) where notation p denotes a prime number and notation n denotes a positive integer. In this case, a hyperelliptic curve C defined over the finite field Fq as a curve of the genus g is expressed by the following equation:y2+h(x)y=f(x)where h(x), f(x)εFq[x] and f(x) is a monic polynomial of an order of (2g+1).
A point −P opposite to a point P (x, y) on the hyperelliptic curve C is defined as (x, y+h(x)). A point for which P=−P is referred to as a ramification point.
As is commonly known, given safety equivalent to that of the elliptic curve cryptography, the processing size (or the number of bits) of a definition body of the hyperelliptic curve cryptography can be reduced to 1/g times the processing size of a definition body of an elliptic curve cryptography. A small processing size provides an implementation merit, which is one of advantages of the hyperelliptic curve cryptography.
Next, fundamentals of the hyperelliptic curve cryptography are explained. As described above, a problem of finding k from D2 can be treated as a discrete logarithmic problem in a Jacobian variety on the hyperelliptic curve and it is possible to treat the problem as a problem in a public-key cryptography where D2 is a divisor defined as a scalar multiplication kD1, k is a multiplier in the scalar multiplication kD1 and D, is a divisor equal to a linear sum of points in the hyperelliptic curve cryptography.
In this case, a divisor is expressed by the following equation:
                              D          =                                                    ∑                i                            ⁢                                                m                  i                                ⁢                                  P                  i                                                      -                                          (                                                      ∑                    i                                    ⁢                                      m                    i                                                  )                            ⁢                              P                ∞                                                    ,                                  ⁢                              m            i                    ≥          0                                    Equation        ⁢                                  ⁢        1            
However, for Pi=(xi, yi) and i≠j, a relation Pi≠Pj holds true. The divisor expressed in this format is referred to as a semi reduced divisor.
Σmi in the above equation is referred to as the weight of the divisor D. A semi reduced divisor having a weight not exceeding the genus g is referred to as a reduced divisor.
In terms of polynomials U and V where U, VεFq[x], any semi reduced devisor D in a Jacobian variety on the hyperelliptic curve can be expressed as D=(U, V). This expression is referred to as a Mumford expression. The Mumford expression is described in documents such as Non-Patent Document 3.U=π(x−xi)mi V(xi)=yi V(x)2+V(x)h(x)−f(x)=0 mod U(x), deg V<deg U  Equation 2
By using the Mumford expression, any reduced divisor D for a genus of 2 can be expressed by a set of polynomials each having elements over the finite field set in the coefficients of the polynomial and having an order not exceeding 2. That is to say, the reduced divisor can be expressed by the following equation:(U, V)=(x2+u1x+u0, v1x+v0)
In addition, by using the Mumford expression, any reduced divisor D with a genus of 3 can be expressed by a set of polynomials each having elements over the finite field set in coefficients of the polynomial and having an order not exceeding 3. That is to say, the reduced divisor can be expressed by the following equation:(U, V)=(x3+u2x2+u1x+u0, v2x2+v1x+v0)
Other expressions of a divisor include a modified Mumford expression and a weighted-coordinate expression. The modified Mumford expression corresponds to projective coordinates in the ECC (elliptic curve cryptography) and expresses the divisor as (U, V, Z), which is obtained by multiplying the Mumford expression (U, V) by a constant Z.
By the same token, the weighted-coordinate expression expresses the divisor as (U, V, Z1, Z2), which is obtained by multiplying the Mumford expression (U, V) by a plurality of constants Z1 and Z2. Both the modified Mumford expression and the weighted-coordinate expression are each used as a technique for reducing the amount of computation of a Harley algorithm described below.
The following pieces of processing on a hyperelliptic curve are explained:    [1] Addition processing (including doubling computation)    [2] Scalar multiplication processing    [3] Base-point generation processing
It is to be noted that, in the following description, the technical term “divisor D” used in this specification is a reduced divisor unless otherwise specified. As described above, a reduced divisor is a semi reduced divisor having a weight not exceeding the genus g.
[1] Addition Processing (Including Doubling Computation)
First of all, an algorithm of addition of points on a hyperelliptic curve is explained.
The scalar multiplication of a divisor can be carried out as a combination of the addition of the divisor and the doubling computation of the divisor. An algorithm of the addition of a divisor is referred to as an addition algorithm. Addition algorithms known so far are explained as follows.
A first proposed practical algorithm is called a Cantor algorithm. The Cantor algorithm is described in Non-Patent Documents 1 and 2. This Cantor algorithm is applicable to a divisor on a hyperelliptic curve of any genus. In comparison with an elliptic curve algorithm, however, the Cantor algorithm has shortcomings that it is complex and entails a large amount of computation.
A Harley algorithm is a proposed addition algorithm limited to hyperelliptic curves each having a genus of 2. According to the Harley algorithm, computation processing is divided into processing cases in accordance with divisor weights, and optimization is applied on a case-by-case basis in order to reduce the amount of computation. On the basis of results of this research on the Harley algorithm, in recent years, various kinds of research are conducted to improve and extend algorithms of computation in the HECC (hyperelliptic curve cryptography).
In accordance with the Harley algorithm, the definition body is used as a prime field and the Mumford expression is adopted as an expression of a divisor on a curve with a genus of 2. Typical research to reduce the amount of computation based on this algorithm is disclosed in Non-Patent Documents 4, 5 and 6. In addition, pieces of typical extended processing with the definition body used as the two extension fields are reported in Non-Patent Documents 7 and 8. Furthermore, pieces of processing extended to the Harley algorithm for a genus of 3 are reported in Non-Patent Documents 9 and 10. On top of that, Non-Patent Documents 11, 12, 6 and 13 disclose researches to reduce the amount of computation by using the Mumford expression to express a divisor and adopting the weighted coordinates.
Processing adopting the Harley algorithm is explained by referring to FIGS. 1 and 2. FIG. 1A is a diagram showing typical processing to find a sum of (D1+D2) where D1 and D2 are each a divisor with a genus of 2. It is to be noted that divisors D1 and D2 are expressed as follows: D1=(U1, V1) and D2=(U2, V2). First of all, the processing is divided into processing cases in accordance with the values of the divisors. That is to say, the addition [D1+D2] of the divisor D1 to the divisor D2 is divided into processing cases in accordance with the values of weights of D1 and D2 as follows:    (1): weight of 2+weight of 2    (2): weight of 2+weight of 1    (3): exception processing 1
Next, in the case of addition of a weight of 2 to a weight of 2 itself, that is, in processing case (1) of a weight of 2+a weight of 2, if the greatest common denominator gcd (U1, U2) for the two divisors D1=(U1, V1) and D2=(U2, V2) is 1 or if gcd (U1, U2)=1, the two divisors D1=(U1, V1) and D2=(U2, V2) do not include a common point or points opposite to each other. In this case, HarleyADD shown in the figure as processing (1a) is carried out. That is to say, addition processing based on the Harley algorithm is carried out. The processing of HarleyADD is processing referred to as a most frequent case disclosed in documents such as Non-Patent Document 7. The most frequent case is a case occurring at the highest probability in the addition processing to find a sum of (D1+D2) of divisors for a genus of 2.
The processing of HarleyADD carried out as a most frequent case in the addition processing to find a sum of divisors for a genus of 2 is shown in Table 1 as follows:
TABLE 1HarleyADD(genus 2)Input: D1 = (u1, v1), deg u1 = 2, D2 = (u2, v2), deg u2 = 2Output: D3 = (u3, v3) = D1 + D21Compute r = res(u1, u2) :4Mw1   u11 + u21, w0   u21w1 + u10 + u20, r   (u10 + u20)w0 + u20w12;2Compute I = i1x + i0 ≡ ru1−1 mod u2i1   w1, i0   w0;3Compute T = t1x + t0 ≡ (v1 + v2)I mod u2:5Mt2   (v11 + v21)w1, t0   (v10 + v20)w0,t1   (v11 + v21 + v10 + v20)(w0 + w1) + t2 + t0,t1   t1 + t2u21, t0   t0 + t2u20;4If t1 = 0 then call sub-procedure.5Compute S = s1x + s0:1I +6Mw2   (rt1)−1, w3   w2r, w4   w2t1, w5   w3r, s1   w4t1 , s0   w4t0;6Compute u3 = x2 + u31x + u30 = s1−2(f + h(Su1 + v1) + (Su1 + v1)2)/u1u2:5Mu31   w1 + w5(1 + w5), u30   u21w1 + u10 + u20 + w5(s0 + s02 + w1);7Compute v3 = v31x + v30 ≡ Su1 + v1 + h mod u3:5Mw1   u11 + u31, w0   u10 + u30 , w2   s1w1, w3   s0w0,w4   (s1 + s0)(w1 + w0) + w2 + w3, w2   w2 + 1, w1   w4 + w2u31,w0   w3 + w2u30, V31   w1 + v11+ h1, v30   w0 + v10 + h0:totalHarleyADD1I +25MEquation 3
The processing of HarleyADD (1a) occurs at a very high probability as will be described later. The probability at which other pieces of typical processing occur is very low. If conditions of the most frequent case are not satisfied, that is, if “the greatest common denominator gcd (U1, U2) for the two divisors D1=(U1, V1) and D2=(U2, V2) is 1” is not satisfied or if “gcd (U1, U2)=1” is not satisfied, exception processing 2 shown in the figure as processing (1b) is carried out.
Also for processing case (2) of a weight of 2+a weight of 1, in the same way, gcd (U1, U2) is checked to determine whether or not gcd (U1, U2)=1. If “gcd (U1, U2)=1” is satisfied, ExHarADD2+1→2 shown in the figure as processing (2a) is carried out. If “gcd (U1, U2)=1” is not satisfied, on the other hand, exception processing 3 shown in the figure as processing (2b) is carried out.
The algorithm of ExHarADD2+1→2 shown in the figure as processing (2a) is disclosed in Non-Patent Document 8. The processing of ExHarADD2+1→2 is shown in Table 3 as follows.
TABLE 3ExHarADD2+1→2Input: D1 = (u1,v1), deg u1 = 1, D2 = (u2,v2), deg u2 = 2Output: D3 = (u3,v3) = D1 + D21Compute r ≡ u2 mod u11Mr   u20 + (u21 + u10)u10.2Compute inverse of u2 mod u1:1Iinv   1/r.3Compute s0 = inv(v1 + v2) mod u1:2Ms0   inv(v10 + v20 + v21u10).4Compute l = s · u2 = s0x2 + l1x + l0:2Ml1   s0u21, l0   s0u20.5Compute k = (f + v2h + v22)/u2 =1Mx3 + k2x2 + k1x + k0:k2   f4 + u21, k1   f3 + (f4 + u21)u21 + v21 + u20.6Compute u3 = (k + s(l + h))/u1 = x2 + u31x + u30:3Mu31   k2 + s02 + s0 + u10,u30   k1 + s0(l1 + h1) + u10u31.7Compute v3 = v31x + v30 ≡ (l + v2) + h mod u3:2Mv31   u31(h2 + s0) + (h1 + l1 + v21),v30   u30(h2 + s0) + (h0 + l0 + v20).total ExHarADD2+1→21I +11MEquation 4
Exception processing 1 shown in the figure as processing case (3) is carried out for a processing case other than processing cases (1) and (2) for weights.
The flow of the doubling multiplication for a genus of 2 is shown in FIG. 1B. The doubling multiplication is processing to compute D+D=2D. Much like the addition, different kinds of processing are carried out in accordance with the weights of the devisor D. The weights of the devisor D are listed as follows:    (4): a weight of 2    (5): a weight of 1 and    (6): a weight of 0
In the case of a weight of 2 for processing case (4), the divisor is checked to determine whether or not the divisor includes a ramification point. If no ramification point is included, HarleyDBL shown in the figure as processing (4a) is carried out. If the divisor includes a ramification point, on the other hand, exception processing 6 shown in the figure as processing (4b) is carried out.
The processing of HarleyDBL shown in the figure as processing (4a) is processing disclosed in documents such as Non-Patent Document 7 as a most frequent case disclosed. The algorithm of the HarleyDBL processing is shown in Table 2 as follows.
TABLE 2HarleyDBL(genus 2)Input: D1 = (u1, v1), deg u1 = 2Output: D3 = (u3, v3) = 2D11Compute r = res(u1, h) :4Mw1   h1 + u11, w0   h0 + u10 + u11w1, r   u10(u10 + h0 + h1w1) + h0w0;2Compute l = i1x + i0 ≡ rh−1 mod u1i1   w1, i0   w0;3Compute T = t1x + t0 ≡ I(f + hv1 + v12)/u1 mod u1:8Mw2   f3 + v11 + v211, w3   v10 + v11(v11 + h1),t1   w0w2 + w1w3, t0   (u11w0 + u10 w1)w2 + w0w3;4If t1 = 0 then goto 5′.5Compute S = s1x + s0:1I +6Mw0   (rt1)−1, w2   w0r, w3   w0t1, w4   w2r, s1   w3t1, s0   w3t0;6Compute u3 = x2 + u31x + u30 = s1−2(f + h(Su1 + v1) + (Su1 + v1)2)/u12:4Mu31   w4(1 + w4), u30   w4(w4(s0(1 + s0)) + w1);7Compute v3 = v31x + v30 ≡ Su1 + v1 + h mod u3:5Mw1   u11 + u31, w0   u10 + u30, w2   s1w1, w3   s0w0,w4   (s1 + s0)(w1 + w0) + w2 + w3, w2   w2 + 1, w1   w4 + w2u31,w0   w3 + w2u30, v31   w1 + v11 + h1, v30   w0 + v10 + h0;totalHarleyDBL1I +27MEquation 5
Next, addition and doubling computation processes for a genus of 3 are explained by referring to FIGS. 2A and 2B. A basic concept adopted for the genus of 3 is the same as that for the genus of 2. In the case of the genus of 3, however, the largest weight of the divisor is 3. Thus, the addition and doubling computation processes for the genus of 3 are characterized in that the number of processing cases is extremely large in comparison with those for the genus of 2.
In the addition processing shown in FIG. 2A, divisors D1 and D2 are expressed as follows: D1=(U1, V1) and D2=(U2, V2). First of all, the processing is divided into processing cases in accordance with the values of the divisors. That is, the addition [D1+D2] to add D1 to D2 is divided into processing cases in accordance with the values of weights D1 and D2 as follows:    (1): weight of 3+weight of 3    (2): weight of 3+weight of 2    (3): weight of 3+weight of 1    (4): exception processing 7
Next, in the case of addition of a weight of 3 to a weight of 3 itself, that is, in processing case (1) of a weight of 3+a weight of 3, if the greatest common denominator gcd (U1, U2) for the two divisors D1=(U1, V1) and D2=(U2, V2) is 1 or if gcd (U1, U2)=1, HarleyADD shown in the figure as processing (1a) is carried out. The processing of HarleyADD 1a is processing referred to as most frequent case for the genus of 3.
The HarleyADD processing, which is the most frequent case in the addition processing to find a sum of divisors with the genus of 3, is disclosed in documents such as Non-Patent Documents 9 and 10. The algorithm adopted in the HarleyADD processing carried out as a most frequent case in the addition processing to find a sum of divisors with the genus of 3 is shown in Table 4 as follows:
TABLE 4HarleyADD(genus 3)Input: D1 = (u1, v1), deg u1 = 3, D2 = (u2, v2), deg u2 = 3Output: D3 = (u3, v3) = D1 + D21Compute r = res(u1, u2):14M2Compute almost inverse inv ≡ r/u1 mod u2:4M3Compute s′ = rs ≡ inv(v1 + v2) mod u2:11M4Compute s = (s′/r) and make s monic:1I +8M5Compute z = su1:6M6Compute u3 = (s(z + w4h) − ws(f + hv1+ v1)/u1)/u2:16M7Compute v3 = −(w3z + h + v1) mod u3:8M8Compute u3 = (f + hv + v2)/u3:8M9Compute v3 = v32x2 + v31x + v30 ≡ v3 + h mod u3:3MtotalHarley ADD1I +78MEquation 6
By the same token, in processing case (2) of a weight of 3+a weight of 2, if “the greatest common denominator gcd (U1, U2) for the two divisors D1=(U1, V1) and D2=(U2, V2) is 1” or if “gcd (U1, U2)=1” is satisfied, ExHarADD3+2→3 shown in the figure as processing (2a) is carried out. If “the greatest common denominator gcd (U1, U2)=1” is not satisfied, on the other hand, exception processing 9 shown in the figure as processing (2b) is carried out.
In the same way, in processing case (3) of a weight of 3+a weight of 1, if “the greatest common denominator gcd (U1, U2) for the two divisors D, =(U1, V1) and D2=(U2, V2) is 1” or if “gcd (U1, U2)=1” is satisfied, ExHarADD3+1→3 shown in the figure as processing (3a) is carried out. If “the greatest common denominator gcd (U1, U2)=1” is not satisfied, on the other hand, exception processing 10 shown in the figure as processing (3b) is carried out.
Since the algorithms of the pieces of processing are not disclosed explicitly in any documents, formulas for the definition body of F2n have been derived. As a result, the algorithms of ExHarADD3+1→3 and ExHarADD3+2→3 are obtained as shown in tables 6 and 7, respectively.
TABLE 6ExHarADD3+1→3Input: D1 = (u1, v1), deg u1 = 3, D2 = (u2, v2), deg u2 = 1Output: D3 = (u3, v3) = D1 + D21Compute r = res(u1, u2):3Mw0   u202, w1   w0(u + 12 + u20), w2   u20u11, r   w1 + w2 + u10.2Compute inverse of u1 mod u2:1Iinv   1/r.3Compute s0 = inv(v1 + v2) mod u2:3Mz0   w0 v12, s0   inv(v10 + v20 + u20v11 + z0).4Compute u3 = (f + hv + v2)/(u1u2), v = s0u1 + v1:12Mu32   S02 + S0 + u20 + u12 + f0t0   F6 + s02 + u12, t1   u12t0, t2   u20u32, t3   h2s0,u31   t1 + t2 + t3 + u11 + v12 + f5,t4   u20(t6 + v12 + f5 + t3 + u11), t5   v12(v12 + u12 + h2),t6   u12(u12(f6 + u12) + f5),u30   w0u32 + t4 + t5 + u12t0 + s0h1 + t6 + u10 + f4 + v11.5Compute v3 = v32x2 + v31x + v30 ≡ s0u1 + v1 + h mod u3:3Mv32   v12 + h2 + s0(u12 + u32) + u32,v31   v11 + h2 + s0(u11 + u31) + u31,v30   v10 + h2 + s0(u10 + u30) + u30.totalExHarADD3+1→31I +21MEquation 7
TABLE 7ExHarADD3+2→3Input: D1 = (u1, v1), deg u1 = 3, D1 = (u2, v2), deg u2 = 2Output: D3 = (u3, v3) = D1 + D21Computer r = res(u1, u2):11Mw0   u202, w1   u112, w2   u212, w3   u12 + u21,w4   w0 + (u20 + u12w3), w5   u21(u10 + u11w3), w5   u20(w5 + w1),w6   w3w2 + u21u11 + u10(u10 + w6), r   w4 + w5 + w62Compute ru1−1 mod u2 ≡ i1x + i0:4Mi2   u21u12, i3   u21u11, i4   u20u12,i1   i2 + w2 + u20 + u11, i0   w2w3 + i3 + i4 + u103Compute t ≡ t1x + t0 = r(v1 + v2)u1−1 mod u2:7Mc1   v11 + v21 + v12u21, c0   v20 + v10 + v12u20,t2   i1c1, t3   i0c0, t1 = t2u21 + (i1 + i0)(c1 + c0) + t2 + t3,t0   t3 + t2u20.4Compute s = 1/r ≡ s1x + s0:1I +6Mz1   rt1, z2   1/z1, z3   z2r, z4   z2t1, z5   z3r, s1   z4t1, s0   z4t0,5Compute v = su1 + v1 ≡ s1x4 + k3x3 + k2x2 + k1x + k0:5Mt0   s0u12, t1   s0u10, t2   s1u11,k3   (s1 + s0)(1 + u12) + s1 + t0, k2   t0 + t2 + v12,k1   (s1 + s0)(u11 + u10) + t2 + t1 + v11, k0   t1 + v10.6Compute u3 = s1−2(f + hv + v2)/(u1u2):11Mu32   z5(z5 + 1) + u12 + u21, t0   k32, t1   u122,t2   z5(z5(f0 + u12 + u21 + t0 + k3) + u21 + h2 + u12),u31   i2 + u11 + u20 + t1 + w2 + t2,t3   (t1 + w2)(u21 + u12) + i3 + i4 + u10,t4   i2 + u20 + w2 + u11 + t1 + f5 + (u21 + u12)(t0 + f0 + k3) + k2,t4   z5(t4 + k3h2) + h2(u12 + u21) + t1 + w2 + i2 + u20 + u11 + h1, t4   z5t4,u30   t3 + t4.7Compute v3 = v32x2 + v31x + v30 ≡ su1 + v1 + h mod u3:8Mt0   s0(u32 + u12), t1   s1(u31 + u11), t2   s1(u12 + u32),v32   t0 + t1 + t2u32 + u32 + v12 + h2,t4   s0(u30 + u10), t5   (s1 + s0)(u31 + u11 + u30 + u10),v31   t5 + t1 + t4 + t2u31 + u31 + v11 + h1,v30   t4 + t2u30 + u30 + v10 + h0.totalExHarADD3+2→31I +52MEquation 8
The flow of the doubling computation for a genus of 3 is shown in FIG. 2B. The doubling computation of a divisor D is processing to compute D+D=2D. Much like the addition, different kinds of processing are carried out in accordance with the weights of the devisor D. The weights of the devisor D are listed as follows:    (5): a weight of 3    (6): a weight of 2    (7): a weight of 1 and    (8): a weight of 0.
In the case of a weight of 3 for weight classification (5) shown above, the divisor is checked to determine whether or not it includes a ramification point. If a ramification point is not included, HarleyDBL shown in the figure as processing (5a) is carried out. If the divisor D includes a ramification point, on the other hand, exception processing 11 shown in the figure as processing (5b) is carried out.
The processing algorithm of HarleyDBL (5a) is disclosed in documents such as Non-Patent Documents 9 and 10 as a most frequent case. The processing algorithm of HarleyDBL 5a is shown in Table 5 as follows:
TABLE 5HarleyDBL(genus 3)Input: D1 = (u1, v1), deg u1 = 3Output: D3 = (u3, v3) = 2D11Compute r = res(u1, h):15M2Compute almost inverse inv ≡ r/h mod u1:4M3Compute z = (f + hv1 + v12)/u1 mod u1:12M4Compute s′ = z · inv mod u1:11M5Compute s = (s′/r) and make s monic:1I +8M6Compute G = su1:6M7Compute u′ =6Ms1−2[(G + w4v1)2 + w4hG + w5(hv1 + f)]:8Compute v′ = Cw3 + h + v1 mod u′:8M9Compute u3 = (f + hv + v2)/u′:8M10 Compute v3 = v′ + h mod u3:3MtotalHarleyDBL1I +81MEquation 9
In the case of both the genuses of 2 and 3, HarleyADD and HarleyDBL are referred to as a most frequent case. If a divisor is generated at random and is subjected to an addition or doubling-computation process, the process becomes HarleyADD or HarleyDBL at a very high probability. It is to be noted that a document such as Non-Patent Document 14 explains HarleyADD and HarleyDBL as processing becoming a most frequent case.
In accordance with Non-Patent Document 14, the probability of becoming processing other than the most frequent case is O (1/q) where notation q denotes the number of elements in the definition body. In safe cryptography applications, qg is a large number having a size of about 160 bits. Thus, in actuality, it is possible to assume a situation in which processing can become only HarleyADD or HarleyDBL.
Thus, if the addition algorithm of the HECC (hyperelliptic curve cryptography) is implemented as cryptography-computation-processing means such as an IC card, only HarleyADD and HarleyDBL are realized. In such an implementation, execution of other complex exception processing most unlikely to occur is not realized in many cases. In such cases, a specific method is adopted. This specific method typically has a configuration for executing a Cantor algorithm, which does not require the division of divisor weights into processing cases. Since the larger the genus, the heavier the load of the complex exception processing, this implementation method is specially described in Non-Patent Documents 9 and 10.
[2]: Scalar Multiplication
Next, scalar multiplication in the algorithm of the HECC (hyperelliptic curve cryptography) is explained.
In the algorithm of the HECC (hyperelliptic curve cryptography), scalar multiplication of a divisor is carried out as a combination of hyperelliptic addition and hyperelliptic doubling computation. The algorithm of the scalar multiplication is explained by taking a basic binary method and a basic double-and-add-always method as examples.
In this case, a binary expression of d is given as follows:(dl−1, - - - , d0), dl−1=1, dl−2, - - - , 0=l or 0.
As a scalar multiplication, the processing algorithm of the basic binary method is described as follows.
Input D0Output D = dD0D   D0for i from l - 2 to 0  {  D   2D  //Harley DBL doubling computation   if di = 1 then D   D + D0  //Harley ADD addition  }return DEquation 10
Next, the processing algorithm of the double-and-add-always method is explained.
A method of acquiring secret information by making use of a problem raised by an implementation method of the cryptography technology is referred to as a side channel attack (SCA). The SCA includes a timing attack (TA), a simple power analysis (SPA) and power attacks such as a differential power analysis (DPA). The timing attack (TA) is described in Non-Patent Document 15 and the power attacks are described in Non-Patent Document 16.
As a measure for the simple power analysis (SPA) and the timing attack (TA) for the elliptic curve cryptography (ECC) as well as the hyperelliptic curve cryptography (HECC), the double-and-add-always method is adopted. Details of the double-and-add-always method are described in Non-Patent Document 17.
As an algorithm of the scalar multiplication, the processing algorithm of the basic double-and-add-always method is expressed as follows.
Input D0Output D = dD0D[0]   D0for i from l - 2 to 0  {  D[0]   2D[0]  //Harley DBL doubling computation   D[1]   D[0] + D0  //Harley ADD addition   D[0]   D[di]  }return D[0]Equation 11[3]: Base-Point Generation
When the scalar computation is applied to a cryptography technology, divisors D0 necessary for the input are divided into the following two types:    (1): a divisor determined in advance and    (2): a divisor undeterminable in advance and generated at random.
In the case of type (1) representing divisors determined in advance, the input divisor is referred to as a base point. A general algorithm for generating a base point is described as follows.    (a): g elements on a definition body Fq are selected at random and g points Pi (where i=1, - - - , g) on a hyperelliptic curve are generated.    (a1): The elements selected at random are used as x coordinates xi (where i=1, - - - , g). Then, such y coordinates are determined for the x coordinates that every point (x, y) is positioned on the hyperelliptic curve.    (b): Let the divisor of the base point be expressed as follows:D0=(U(x), V(x))    (b1): U(x)=(x−x1)(x−X2) - - - (x−xg)    (b2): Coefficients vi of an equation V (x)=vg−1xg−1+vg−2xg−2+ - - - +v0 are determined. If the generated points are all different from each other, for example, the coefficients vi can be found from an equation V (xi)=yi.    (c): The divisors generated in accordance with the above algorithm are each a divisor with a weight equal to the genus g.
If the computation of the scalar multiplication is applied to the cryptography technology, a divisor D0 required in the input is generated. That is, a base point is generated. In the process to generate the base point, if divisors determined in advance are applied, it is possible to find a divisor with a weight equal to the genus g as a divisor usable as a base point by carrying out the processes (a) to (c).
[Non-Patent Document 1]
N. Koblitz. Hyperelliptic curve cryptosystems. J. Cryptology, vol. 1, No. 3, pp. 139-150, 1989.
[Non-Patent Document 2]
D. G. Cantor. Computing in the Jacobian of hyperelliptic curve. Math. Comp., Vol. 48, No. 177, pp. 95-101, 1987.
[Non-Patent Document 3]
D. Mumford, Tata lectures on theta II, Progress in Mathematics, no. 43, Birkhauser, 1984.
[Non-Patent Document 4]
K. Matsuo, J. Chao and S. Tsujiii. Fast Genus two hyperelliptic curve cryptosystems. Technical Report ISEC2001-31, IEICE Japan, 2001.
[Non-Patent Document 5]
M. Takahashi. Improving Harley algorithms for Jacobians of genus 2 hyperelliptic curves. SCIS2002. (Japanese).
[Non-Patent Document 6]
T. Lange. Inversion-free arithmetic on genus 2 hyperelliptic curves. Cryptology eprint Archive, 2002/147, IACR, 2002.
[Non-Patent Document 7]
T. Sugizaki, K. Matsuo, J. Chao and S. Tsujiii. An extension of Harley addition algorithm for hyperelliptic curves over finite fields of characteristic two. ISEC2002-9, IEICE, 2001.
[Non-Patent Document 8]
T. Lange. Efficient arithmetic on genius 2 hyperelliptic curves over finite fields via explicit formulae. Cryptology ePrint Archive, 2002/121, IACR, 2002.
[Non-Patent Document 9]
J. Kuroki, M. Gonda, K. Masuo, J. Chao and S. Tsujii. Fast genus three hyperelliptic curve cryptosystems. SCIS2002.
[Non-Patent Document 10]
J. Pelzl, T. Wollinger, J. Guajardo and C. Paar. Hyperelliptic curve Cryptosystems: Closing the Performance Gap to Elliptic Curves. Cryptology eprint Archive, 2003/026, IACR, 2003.
[Non-Patent Document 11]
Y. Miyamoto, H. Doi, K. Masuo, J. Chao and S. Tsujii. A fast addition algorithm of genus two hyperelliptic curves. SCI2002. (Japanese).
[Non-Patent Document 12]
N. Takahashi, H. Morimoto and A. Miyaji. Efficient exponentiation on genus two hyperelliptic curves (II). ISEC2002-145, IEICE, 2003. (Japanese).
[Non-Patent Document 13]
T. Lange. Weighed coordinate on genus 2 hyperelliptic curve. Cryptology ePrint Archive, 2002/153, IACR, 2002.
[Non-Patent Document 14]
N. Nagao. Improving group law algorithms for Jacobians of hyperelliptic curves. ANTS-IV, LNCS 1838, pp. 439-448, Springer-Verlag, 2000.
[Non-Patent Document 15]
C. Kocher. Timing Attacks on Implementations of Diffie-Helman, RSA, DSS and Other Systems, CRYPTO '96, LNCS 1109, pp. 104-113, 1996.
[Non-Patent Document 16]
C. Kocher, J. Jaffe and B. Jun. Differential Power Analysis, CRYPTO '99, LNCS 1666, pp. 388-397, Springer-Verlag, 1999.
[Non-Patent Document 17]
J.-S. Coron. Resistance against Differential Power Analysis for Elliptic Curve Cryptosystems, CHES '99, LNCS 1717, pp. 292-302, Springer-Verlag, 1999.